#pragma once

#include <vector>
//#include <bitset>
#include "utils/typedef.h"
#include "connectivity_set.h"
#include "sparse_set.h"
#include "sp_set.h"
#include "macros.h"
#include "math.h"
#include "config.h"
#include "context.h"
#include "fast_reset_flag_array.h"

namespace mcgpp {
  struct Metrics;
  //缩合备忘录
  struct Memento {
    //代表节点
    const IDType u;
    // 被缩合掉的节点
    const IDType v;
  };
  namespace ds {

    class Vertex {
    public:
      explicit Vertex(const WeightType weight) :
              _incident_nets(),
              _weight(weight) {}

      Vertex() :
              _incident_nets(),
              _weight(1) {}

      Vertex(const Vertex &) = default;

      Vertex &operator=(const Vertex &) = default;

      Vertex(Vertex &&) = default;

      Vertex &operator=(Vertex &&) = default;

      ~Vertex() = default;

      // ! Disables the hypernode/hyperedge. Disable hypernodes/hyperedges will be skipped
      // ! when iterating over the set of all nodes/edges.
      void disable() {
        _valid = false;
      }

      bool isDisabled() const {
        return _valid == false;
      }

      void enable() {
        _valid = true;
      }

      IDType size() const {
        return _incident_nets.size();
      }

      WeightType weight() const {
        return _weight;
      }

      std::vector<IDType> &incidentNets() {
        return _incident_nets;
      }

      const std::vector<IDType> &incidentNets() const {
        return _incident_nets;
      }

      void setWeight(WeightType weight) {
        _weight = weight;
      }

      //is_permutation判断前一个序列是否是后一个序列的一个排列 O(n^2)
      bool operator==(const Vertex &rhs) const {
        return _incident_nets.size() == rhs._incident_nets.size() &&
               _weight == rhs._weight &&
               _valid == rhs._valid &&
               std::is_permutation(_incident_nets.begin(),
                                   _incident_nets.end(),
                                   rhs._incident_nets.begin());
      }

      bool operator!=(const Vertex &rhs) const {
        return !operator==(rhs);
      }

    public:
      PartitionID part_id = -1;

      ll cut_edge_weight = 0;
      ll total_edge_weight = 0;//内部边总权重 = total_edge_weight - cut_edge_weight

      ll cut_edge_num = 0;
      ll total_edge_num = 0;

      //节点关联的切边数目
      IDType num_incident_cut_es = 0;
      // ! State during local search: inactive/active/marked
      uint32_t state = 0;

    private:
      std::vector<IDType> _incident_nets;
      // ! Hypernode/Hyperedge weight
      WeightType _weight = 1;
      // ! Flag indicating whether or not the element is active.
      bool _valid = true;

    };

    class Edge {
    public:

      /*!
       * Constructs a edge.
       * \param begin The incidence information starts at _incidence_array[begin]
       * \param size  The number of incident nets (for hypernodes), the number of pins (for hyperedges)
       * \param weight The weight of the hypernode/hyperedge
       */
      Edge(const IDType begin, const IDType size,
           const WeightType weight) :
              _begin(begin),
              _size(size),
              _weight(weight) {}

      Edge() = default;

      Edge(const Edge &) = default;

      Edge &operator=(const Edge &) = default;

      Edge(Edge &&) = default;

      Edge &operator=(Edge &&) = default;

      ~Edge() = default;

      // ! Disables the hypernode/hyperedge. Disable hypernodes/hyperedges will be skipped
      // ! when iterating over the set of all nodes/edges.
      void disable() {
        _valid = false;
      }

      bool isDisabled() const {
        return _valid == false;
      }

      void enable() {
        _valid = true;
      }

      // ! Returns the index of the first element in _incidence_array
      IDType firstEntry() const {
        return _begin;
      }

      // ! Sets the index of the first element in _incidence_array to begin
      void setFirstEntry(IDType begin) {
        _begin = begin;
        _valid = true;
      }

      // ! Returns the index of the first element in _incidence_array
      IDType firstInvalidEntry() const {
        return _begin + _size;
      }

      IDType size() const {
        return _size;
      }

      void setSize(IDType size) {
        _size = size;
      }

      void incrementSize() {
        ++_size;
      }

      void decrementSize() {
        --_size;
      }

      WeightType weight() const {
        return _weight;
      }

      void setWeight(WeightType weight) {
        _weight = weight;
      }

      bool operator==(const Edge &rhs) const {
        return _begin == rhs._begin && _size == rhs._size && _weight == rhs._weight;
      }

      bool operator!=(const Edge &rhs) const {
        return !operator==(rhs);
      }

    private:
      // ! Index of the first element in _incidence_array
      IDType _begin = 0;
      // ! Number of _incidence_array elements
      IDType _size = 0;
      // ! Hypernode/Hyperedge weight
      WeightType _weight = 1;
      // ! Flag indicating whether or not the element is active.
      bool _valid = true;
    };

    class GenericGraph {
      static int constexpr bits = 10;//保留十位
    public:
      //存储每个分区的信息
      class PartInfo {
      public:
        bool operator==(const PartInfo &other) const {
          return weight == other.weight && t_weight == other.t_weight;
        }

        WeightType weight; // 这个分区中节点的权重总和
        WeightType num;//总节点的边的个数
        WeightType t_weight;//实际weight
      };

      static constexpr int32_t kInvalidPartition = -1;

      GenericGraph(const IDType num_nodes,
                   const IDType num_edges,
                   const IDType num_pins,

                   const IDType *index_vector,
                   const IDType *edge_vector,
                   const PartitionID k = 2) :
              _num_nodes(num_nodes), _num_edges(num_edges), _k(k),
              _current_num_nodes(num_nodes), _current_num_edges(num_edges), _current_node_set(num_nodes),
              _nodes(num_nodes, Vertex(1)), _edges(num_edges, Edge(0, 0, 1)),
              _part_info(k), _incidence_array(num_pins, 0),
              _e_not_containing_u(num_edges), _connectivity_sets(num_edges) {

        //构建每一条边
        IDType edge_vector_index = 0;
        for (IDType i = 0; i < num_edges; ++i) {
          edge(i).setFirstEntry(index_vector[i]);
          int sz = index_vector[i + 1] - index_vector[i];
          if (sz > 2) {
            DBG << sz;
            ERROREXIT("error!");
          }
          edge(i).setSize(sz);

          for (IDType pin_idx = index_vector[i]; pin_idx < index_vector[i + 1]; ++pin_idx) {
            _incidence_array[edge_vector_index] = edge_vector[edge_vector_index];
            ++edge_vector_index;
            //构建邻接矩阵
            IDType pin = edge_vector[pin_idx];
            node(pin).incidentNets().emplace_back(i);
          }
        }

        //构建节点
        for (int i = 0; i < num_nodes; ++i) {
          _current_node_set.add(i);
          //初始化权重
          node(i).setWeight(node(i).incidentNets().size());
          //初始化总边权重
          node(i).total_edge_weight = node(i).incidentNets().size();
          //初始化总边数目
          node(i).total_edge_num = node(i).incidentNets().size();
        }

        //添加一个哨兵节点，还原的时候使用
        _edges.emplace_back(edge(_num_edges - 1).firstInvalidEntry(), 0, 0);

      }

      void printGraph(int d = 0) {
        LOG << "---------------------------------------------";
        LOG << "current num node:" << _current_num_nodes;
        LOG << "current num edge:" << _current_num_edges;
        LOG << "";
        LOG << "node info:";

        for (IDType i: _current_node_set) {
          std::cout << "node " << i + d << " (" << node(i).weight() << ") " << " : size = "
                    << node(i).incidentNets().size()
                    << " -> ";
          for (auto &e: node(i).incidentNets()) {

            auto begin = edge(e).firstEntry();
            auto end = edge(e).firstInvalidEntry();
            for (auto it = begin; it != end; ++it) {
              auto pin = _incidence_array[it];
              if (pin != i)
                std::cout << "id:" << pin + d << " " << edge(e).weight() << "\t";

            }
          }
          LOG << "";
        }
        LOG << "";
      }

      //缩合两个点u,v
      void contract(IDType u, IDType v) {
        node(u).setWeight(node(u).weight() + node(v).weight());
        node(u).total_edge_weight += node(v).total_edge_weight;//合并两个顶点总权重应该会减少，主要是单点边的权重
        node(u).cut_edge_weight += node(v).cut_edge_weight;//切边权重是不会变的

        node(u).total_edge_num += node(v).total_edge_num;//合并两个顶点总边数应该会减少，主要是单点边的数目
        node(u).cut_edge_num += node(v).cut_edge_num;//切边数目是不会变的

        node(v).cut_edge_weight = 0;// 还原的时候重新计算
        node(v).cut_edge_num = 0;

        //遍历v的所有邻边
        for (IDType e: node(v).incidentNets()) {
          const int pins_begin = edge(e).firstEntry();
          const int pins_end = edge(e).firstInvalidEntry();
          int slot_of_u = pins_end - 1;
          int last_pin_slot = pins_end - 1;
          for (int pin_iter = pins_begin; pin_iter != last_pin_slot; ++pin_iter) {
            int pin = _incidence_array[pin_iter];
            if (pin == v) {
              //交换v到最后
              std::swap(_incidence_array[pin_iter], _incidence_array[last_pin_slot]);
              --pin_iter;
            } else if (pin == u)
              slot_of_u = pin_iter;
          }

          if (slot_of_u != last_pin_slot) {
            //case1:说明这条边是u,v的公共边
            edge(e).decrementSize();
            if (partID(v) != kInvalidPartition) {
              //修改分区信息
              decrementPinCountInPart(e, partID(v));
            }

          } else {
            //case2:说明这条边是V的私有边，需要替换v为u
            _incidence_array[edge(e).firstInvalidEntry() - 1] = u;
            node(u).incidentNets().emplace_back(e);
          }
        }
        //删除点v
        node(v).disable();
        --_current_num_nodes;
        _current_node_set.remove(v);
      }

      //还原两个点
      void uncontract(const Memento &memento) {
        //更新基本信息
        ++_current_num_nodes;
        node(memento.v).enable();
        _current_node_set.add(memento.v);

        node(memento.u).setWeight(node(memento.u).weight() - node(memento.v).weight());
        node(memento.u).total_edge_weight -= node(memento.v).total_edge_weight;//合并两个顶点总权重应该会减少，主要是单点边的权重
        node(memento.u).total_edge_num -= node(memento.v).total_edge_num;//合并两个顶点总权重应该会减少，主要是单点边的权重
        node(memento.v).part_id = node(memento.u).part_id;
        //标记v的边
        _e_not_containing_u.reset();
        for (const IDType &e: node(memento.v).incidentNets())
          _e_not_containing_u.set(e, true);
        //遍历u的边还原
        const auto &nets_of_u = node(memento.u).incidentNets();
        size_t incident_edge_end = nets_of_u.size();

        for (size_t incident_edge_it = 0; incident_edge_it != incident_edge_end; ++incident_edge_it) {
          const IDType e_id = nets_of_u[incident_edge_it];
          if (_e_not_containing_u[e_id]) {
            //这条边要么是u，v的公共边,要么是v的私有边
            if (edge(e_id).firstInvalidEntry() < edge(e_id + 1).firstEntry() &&
                _incidence_array[edge(e_id).firstInvalidEntry()] == memento.v) {
              //u,v的公共边,这条边也不可能是切边,size + 1
              edge(e_id).incrementSize();
              //增加一个pin
              _connectivity_sets[e_id].add(partID(memento.v));

            } else {
              //v的私有边，因为size没变,从u中删除这条边
              std::swap(node(memento.u).incidentNets()[incident_edge_it], node(memento.u).incidentNets().back());
              node(memento.u).incidentNets().pop_back();
              //更新索引
              --incident_edge_it;
              --incident_edge_end;
              //替换u -> v
              int pin_end = edge(e_id).firstInvalidEntry() - 1;
              while (_incidence_array[pin_end] != memento.u)
                --pin_end;
              _incidence_array[pin_end] = memento.v;

              //这条边的连通性应该是不变的，part(v) == part(u)
              if (_connectivity_sets[e_id].bit() == 3) {
                //如果是切边的话，更新切边权重
                node(memento.u).cut_edge_weight -= edge(e_id).weight();
                node(memento.v).cut_edge_weight += edge(e_id).weight();
                node(memento.u).cut_edge_num -= 1;
                node(memento.v).cut_edge_num += 1;
              }
            }
          }
          //否则是u的私有边,不用考虑
        }
      }

      //从顶点v的邻接链表中删除边e
      MCGPP_ATTRIBUTE_ALWAYS_INLINE void removeIncidentEdgeFromNode(const IDType e,
                                                                    const IDType v) {
        auto begin = node(v).incidentNets().begin();
        auto last_entry = node(v).incidentNets().end() - 1;
        while (*begin != e) {
          ++begin;
        }
        std::swap(*begin, *last_entry);
        node(v).incidentNets().pop_back();
      }

      //移动节点分区并更新切点集合
      void changeNodePart(IDType v, PartitionID from, PartitionID to, sp::SparseSet<int> &cut_nodes) {
        //更新边的属性和邻局的切边权重
        for (const IDType &e: node(v).incidentNets()) {
          decrementPinCountInPart(e, from);
          incrementPinCountInPart(e, to);

          if (_connectivity_sets[e].bit() == 3) {
            //内部边 -> 边界边 增加cut
            for (auto i = edge(e).firstEntry(); i != edge(e).firstInvalidEntry(); ++i) {
              IDType pin = _incidence_array[i];
              if (node(pin).cut_edge_weight == 0)
                cut_nodes.add(pin);
              node(pin).cut_edge_weight += edge(e).weight();
              node(pin).cut_edge_num += 1;
            }
          } else {
            //边界边 -> 内部边
            for (auto i = edge(e).firstEntry(); i != edge(e).firstInvalidEntry(); ++i) {
              IDType pin = _incidence_array[i];
              node(pin).cut_edge_weight -= edge(e).weight();
              node(pin).cut_edge_num -= 1;
              if (node(pin).cut_edge_weight == 0)
                cut_nodes.remove(pin);
            }
          }
        }
        //更新block的体积
        updatePartInfo(v, from, to);
      }



      //n-level需要，将没有被标记的顶点加入进来
      void changeNodePart(IDType v, PartitionID from, PartitionID to, sp::SparseSet<int> &cut_nodes,
                           ds::FastResetFlagArray<>&_marked) {
        //更新边的属性和邻局的切边权重
        for (const IDType &e: node(v).incidentNets()) {
          decrementPinCountInPart(e, from);
          incrementPinCountInPart(e, to);

          if (_connectivity_sets[e].bit() == 3) {
            //内部边 -> 边界边 增加cut
            for (auto i = edge(e).firstEntry(); i != edge(e).firstInvalidEntry(); ++i) {
              IDType pin = _incidence_array[i];
              if (node(pin).cut_edge_weight == 0 && !_marked[pin])
                cut_nodes.add(pin);
              node(pin).cut_edge_weight += edge(e).weight();
              node(pin).cut_edge_num += 1;
            }
          } else {
            //边界边 -> 内部边
            for (auto i = edge(e).firstEntry(); i != edge(e).firstInvalidEntry(); ++i) {
              IDType pin = _incidence_array[i];
              node(pin).cut_edge_weight -= edge(e).weight();
              node(pin).cut_edge_num -= 1;
              if (node(pin).cut_edge_weight == 0)
                cut_nodes.remove(pin);
            }
          }
        }
        //更新block的体积
        updatePartInfo(v, from, to);
      }

      //评估移动节点的收益delta: delta < 0 更好的电导
      ll moveNodeGain(IDType v, PartitionID from, PartitionID to, ll cut, ll cur_cond) {
        cut += node(v).total_edge_weight - 2 * node(v).cut_edge_weight;
        ll volume = std::min(_part_info[from].weight - node(v).weight(),
                             _part_info[to].weight + node(v).weight());


        return static_cast<ll>((static_cast<double>(cut) / volume) * bits) - cur_cond;
      }

      //删除一条单点边
      void removeEdge(IDType u, IDType e) {
        if (edge(e).size() != 1)
          ERROREXIT("single edge error!");

        node(u).total_edge_weight -= 2 * edge(e).weight();
        _part_info[partID(u)].weight -= 2 * edge(e).weight();
        node(u).total_edge_num -= 2;
        _part_info[partID(u)].num -= 2;

        //pin删除边e
        removeIncidentEdgeFromNode(e, u);
        _connectivity_sets[e].clear();
        edge(e).disable();
        --_current_num_edges;
      }

      //恢复一条被删除的单点边
      void restoreEdge(IDType e) {
        ++_current_num_edges;
        edge(e).enable();
        //这里只遍历一个点
        IDType u = _incidence_array[edge(e).firstEntry()];
        node(u).incidentNets().emplace_back(e);
        if (partID(u) != kInvalidPartition)
          incrementPinCountInPart(e, partID(u));

        node(u).total_edge_weight += 2 * edge(e).weight();
        _part_info[partID(u)].weight += 2 * edge(e).weight();
        node(u).total_edge_num += 2;
        _part_info[partID(u)].num += 2;
      }

      //删除一条平行边
      void removeEdge(IDType e) {
        int begin = edge(e).firstEntry();
        int end = edge(e).firstInvalidEntry();

        for (auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it) {
          IDType pin = _incidence_array[it];
          --node(pin).total_edge_num;
          if (_connectivity_sets[e].bit() == 3)
            --node(pin).cut_edge_num;
          --_part_info[partID(pin)].num;
        }
        for (auto pin_iter = begin; pin_iter != end; ++pin_iter) {
          int pin = _incidence_array[pin_iter];
          //pin删除边e
          removeIncidentEdgeFromNode(e, pin);
        }
        _connectivity_sets[e].clear();
        edge(e).disable();
        --_current_num_edges;
      }

      //恢复一条被删除的平行边e,e是被删除的
      void restoreEdge(IDType e, IDType old_representative) {
        ++_current_num_edges;
        edge(e).enable();
        for (auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it) {
          IDType pin = _incidence_array[it];
          node(pin).incidentNets().emplace_back(e);
          if (partID(pin) != kInvalidPartition)
            incrementPinCountInPart(e, partID(pin));
        }
        for (auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it) {
          IDType pin = _incidence_array[it];
          ++node(pin).total_edge_num;
          if (_connectivity_sets[e].bit() == 3)
            ++node(pin).cut_edge_num;
          ++_part_info[partID(pin)].num;
        }
      }


      //增加一条边对某个分区的占用
      void incrementPinCountInPart(IDType e, PartitionID p_id) {
//        LOG<<"edge"<<e<<"add partition"<<p_id;
        _connectivity_sets[e].add(p_id);
//        if(_connectivity_sets[e].bit() == 3){
//          //变成切边了
//          for(auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it)
//            node(_incidence_array[it]).cut_edge_weight += edge(e).weight();
//        }
      }

      //减少一条边对某个分区的占用
      void decrementPinCountInPart(IDType e, PartitionID p_id) {
//        if(_connectivity_sets[e].bit() == 3){
//          //不再是切边了
//          for(auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it)
//            node(_incidence_array[it]).cut_edge_weight -= edge(e).weight();
//        }
        _connectivity_sets[e].remove(p_id);

      }


      //设置一个顶点的分区
      void setNodePart(IDType n_id, PartitionID id) {
        updatePartInfo(n_id, id);
        for (auto &e: node(n_id).incidentNets()) {
          bool not_cut_edge = _connectivity_sets[e].bit() != 3;
          incrementPinCountInPart(e, id);
          if (not_cut_edge && _connectivity_sets[e].bit() == 3) {
            for (auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it) {
              node(_incidence_array[it]).cut_edge_weight += edge(e).weight();
              node(_incidence_array[it]).cut_edge_num += 1;

            }
          }
        }

      }

      //移除一个顶点
      void unsetNodePart(const IDType n_id) {
        for (auto &e: node(n_id).incidentNets()) {
          if (_connectivity_sets[e].bit() == 3) {
            for (auto it = edge(e).firstEntry(); it != edge(e).firstInvalidEntry(); ++it) {
              node(_incidence_array[it]).cut_edge_weight -= edge(e).weight();
            }
          }
          decrementPinCountInPart(e, partID(n_id));
        }
        updatePartInfo(n_id, partID(n_id), kInvalidPartition);
      }

      //顶点分区变更后，更新每个分区的信息,
      void updatePartInfo(const IDType u, const PartitionID id) {
        node(u).part_id = id;
        _part_info[id].weight += node(u).total_edge_weight;
        _part_info[id].t_weight += node(u).weight();
        _part_info[id].num += node(u).total_edge_num;
      }

      void updatePartInfo(const IDType u, const PartitionID from, const PartitionID to) {
        node(u).part_id = to;
        _part_info[from].weight -= node(u).total_edge_weight;
        _part_info[from].t_weight -= node(u).weight();
        _part_info[from].num -= node(u).total_edge_num;

        if (to != kInvalidPartition) {
          _part_info[to].weight += node(u).total_edge_weight;
          _part_info[to].t_weight += node(u).weight();
          _part_info[to].num += node(u).total_edge_num;

        }

      }


      IDType initialNumNodes() const {
        return _num_nodes;
      }

      IDType initialNumEdges() const {
        return _num_edges;
      }

      //节点是否合法，被缩合后的点不再合法,Returns true if the node is enabled
      bool nodeIsEnabled(const IDType u) {
        return !node(u).isDisabled();
      }

      //true 表示边是合法的
      bool edgeIsEnabled(const IDType e) {
        return !edge(e).isDisabled();
      }

      Vertex &node(const IDType u) {
        return _nodes[u];
      }

      Edge &edge(const IDType e) {
        return _edges[e];
      }

      //计算一条边的hash值，O(1)操作
      int64_t edgeHash(const IDType e) {
        int64_t val = 0;
        auto begin = edge(e).firstEntry();
        auto end = edge(e).firstInvalidEntry();
        for (int i = begin; i < end; ++i)
          val += math::hash(static_cast<int64_t>(_incidence_array[i]));
        return val;
      }

      IDType edgeSize(const IDType e) {
        return edge(e).size();
      }

      PartitionID partID(const IDType u) {
        return node(u).part_id;
      }


      //check每个点和每条边的更新是否有误
      void check() {
        for (int i = 0; i < _num_edges; ++i) {
          if (edgeIsEnabled(i) == false)
            continue;
          if (_connectivity_sets[i].size() == 0) {
            LOG << _connectivity_sets[i].size() << _connectivity_sets[i].bit();
            ERROREXIT("error!");
          }

          int bit = 0;
          for (auto it = edge(i).firstEntry(); it != edge(i).firstInvalidEntry(); ++it) {
            auto pin = _incidence_array[it];
            auto pid = node(pin).part_id;
            bit |= 1 << pid;
            if (_connectivity_sets[i].contains(pid) == false) {
              LOG << bit << _connectivity_sets[i].bit();
              ERROREXIT("error!");
            }
          }
          if (bit != _connectivity_sets[i].bit()) {
            LOG << bit << _connectivity_sets[i].bit();
            ERROREXIT("error!");
          }

        }

        for (int i = 0; i < _num_nodes; ++i) {
          if (nodeIsEnabled(i) == false) {
            if(_current_node_set.contains(i))
              ERROREXIT("error");
            continue;
          }
          else{
            if(_current_node_set.contains(i) == false)
              ERROREXIT("error!");
          }
          int total_edge_weight = 0;
          int cut_edge_weight = 0;
          int total_edge_num = 0;
          int cut_edge_num = 0;
          for (auto e: node(i).incidentNets()) {
            total_edge_weight += edge(e).weight();
            total_edge_num += 1;
            if (_connectivity_sets[e].bit() == 3) {
              cut_edge_weight += edge(e).weight();
              cut_edge_num += 1;
            }
          }
          if (total_edge_weight != node(i).total_edge_weight) {
            LOG << "node " << i << " error!";
            LOG << total_edge_weight << "!=" << node(i).total_edge_weight;
            ERROREXIT();
          }
          if (cut_edge_weight != node(i).cut_edge_weight) {
            LOG << "node " << i << " error!";
            LOG << cut_edge_weight << "!=" << node(i).cut_edge_weight;
            ERROREXIT();
          }
          if (total_edge_num != node(i).total_edge_num) {
            LOG << "node " << i << " error!";
            LOG << total_edge_num << "!=" << node(i).total_edge_num;
            LOG<<"edge sz:"<< node(i).incidentNets().size();
            ERROREXIT();
          }
          if (cut_edge_num != node(i).cut_edge_num) {
            LOG << "node " << i << " error!";
            LOG << cut_edge_num << "!=" << node(i).cut_edge_num;
            ERROREXIT();
          }
        }
      }


      IDType _num_nodes; //初始图顶点数目
      IDType _num_edges; //初始图边数目
      PartitionID _k; //划分个数，其实就说2

      WeightType _total_weight; //所有顶点的总权重

      IDType _current_num_nodes;//缩合后当前顶点数目
      IDType _current_num_edges;//缩合后当前边数目
      ds::SparseSet<> _current_node_set;//当前的顶点集合

      std::vector<IDType> _incidence_array;//存所有边的pin
      std::vector<Vertex> _nodes;//存所有节点
      std::vector<Edge> _edges;//存所有边



      std::vector<ConnectivitySet> _connectivity_sets;//每条边的连接信息
      std::vector<PartInfo> _part_info;//每个分区的划分信息，也就是两个

      //还原点需要使用，u,v合并会导致u中既有u自己的边，也有v自己的边
      ds::FastResetFlagArray<> _e_not_containing_u;


    };
  }
}